﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.Algorithms.UnionFind
{
    /*Aim - To find whether two objects in a network are connected
     * The objects are placed in an array 0 to N-1
     * Conceptually they form a tree. i.e each element i will have array[i] = its parent
     * if q = parent(p) , array[p] = q. if r = parent(q), array[q] = r, so on.
     * if r is a root, array[r] = r
     * IsConnected(p,q) => True if Root(p) = Root(q)
     * Union(p,q) => Find root(q) and then set it to root(p). root(p) resides in array[root(p)]
     * */
    class QuickUnion
    {
        private int[] _array;
        private int _count = 0;

        public QuickUnion(int N)
        {
            _count = N;
            _array = new int[N];

            for (int i = 0; i < _count; i++)
            {
                _array[i] = i;
            }
        }

        /// <summary>
        /// Time Complexity - O(N)
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public bool Union(int p, int q)
        {
            try
            {
                int root_p = Root(p);
                int root_q = Root(q);

                // set root(p) = root(q)
                _array[root_p] = root_q;

                return true;
            }
            catch (Exception)
            {                
                return false;
            }
        }

        private int Root(int i)
        {
            // Go to array[i] and then traverse the array till root is reached
            // Root is reached when array[i] = i

            while (i != _array[i])
            {
                i = _array[i];
            }

            return i;
        }

        /// <summary>
        /// Time Complexity O(N)
        /// </summary>
        /// <param name="p"></param>
        /// <param name="q"></param>
        /// <returns></returns>
        public bool IsConnected(int p, int q)
        {
            return Root(p) == Root(q);
        }

    }
}
